

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" type="image/png" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="Yuchen">
  <meta name="keywords" content="">
  <title>金总的算法课 - Yuchen&#39;s Blog</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/tomorrow-night-eighties.min.css" />
    
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_pf9vaxs7x7b.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end --><meta name="generator" content="Hexo 5.1.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>Yuchen's Blog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('/img/main4.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-11-19 00:00" pubdate>
        2020年11月19日 凌晨
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      4.1k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      52
       分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">金总的算法课</h1>
            
            <div class="markdown-body" id="post-body">
              <h2 id="算法课笔记">算法课笔记</h2>
<h3 id="月14日-lead-in">9月14日 Lead-in</h3>
<p>本课程主要内容：分支、动态规划、贪心、随机算法、近似算法、NP-完全性理论</p>
<blockquote>
<p><strong>课堂习题</strong></p>
<p>LeetCode 440题目描述：给定整数 <span class="math inline">\(n\)</span> 和 <span class="math inline">\(k\)</span>，找到 <span class="math inline">\(1\)</span> 到 <span class="math inline">\(n\)</span> 中字典序第 <span class="math inline">\(k\)</span> 小的数字。</p>
<p>注意：<span class="math inline">\(1 \leq k \leq n \leq 10^9\)</span> 。</p>
</blockquote>
<blockquote>
<p><strong>解题思路</strong></p>
<p>如图，字典序构成了一棵十叉树，该树的每一层代表具体某一位置的数字（如，个十百千万）。比如根节点代表最高位的数字，子树的根节点代表低一位的数字，直到叶子节点表示个位的数字。如此，构造出的树的高度（根节点高度为0）应为（ <span class="math inline">\(\lfloor lg(n+1) \rfloor + 1\)</span>）。<font color = "#FF0000">!这里高度还存在一点问题，准确说是9棵十叉树</font></p>
<p>但是由于 <span class="math inline">\(n\)</span> 大小的限制，构成的并不是一个满十叉树。比如示例中 <span class="math inline">\(1\)</span> 只有 <span class="math inline">\([10,11,12,13]\)</span> 四个孩子。</p>
<p>该问题转化为求解区间 <span class="math inline">\([1,n+1)\)</span> 计数的问题，无需构建真实的树。若当前根的数字为 <span class="math inline">\(l\)</span> ，则右侧相邻兄弟结点为 <span class="math inline">\(l+1\)</span> ，计算树结点区间 <span class="math inline">\([l,l+1)\)</span> 的结点个数（ 记作 <span class="math inline">\(cnt\)</span>） ，计数时一层一层向下，需要递归（迭代也行）地计算子树的结点个数。若当前树结点区间的结点个数 <span class="math inline">\(cnt \le k\)</span> ，则说明目标数字不在当前区间，而在右侧区间 <span class="math inline">\([l+1,l+2)、[l+2,l+3)...\)</span> 之一中，则 <span class="math inline">\(k = k-num\)</span> ，对右侧相邻区间计数；若当前区间的结点个数 <span class="math inline">\(cnt &gt; k\)</span> ，则说明目标数字在当前结点区间<span class="math inline">\([l,l+1)\)</span> 内，则应在当前区间的子树下寻找，也就是以 <span class="math inline">\(l\)</span> 为根的子树下寻找。重复上述过程，直至找到目标数字（即 <span class="math inline">\(k=0\)</span> 时的数字）。</p>
<p>使用游标“指针” <span class="math inline">\(cur\)</span> 存储当前指向的数字，刚开始为 <span class="math inline">\(1\)</span> ，根据下图树的结构，游标在兄弟结点间向右侧区间移动，<span class="math inline">\(cur = cur + 1\)</span> ；若向孩子自己的子树（第一个孩子结点移动，则 <span class="math inline">\(cur = cur \times 10\)</span> 。</p>
<p><img src="Snipaste_2020-09-14_19-48-31.png" srcset="/img/loading.gif" /></p>
<p><img src="Snipaste_2020-09-14_19-04-50.png" srcset="/img/loading.gif" /></p>
</blockquote>
<div class="hljs"><pre><code class="hljs C++"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span>
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">findKthNumber</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> k)</span> </span>&#123;
		<span class="hljs-keyword">int</span> cur = <span class="hljs-number">1</span>;
        k -= <span class="hljs-number">1</span>; <span class="hljs-comment">// 减去根节点 1 </span>
        <span class="hljs-keyword">while</span>(k &gt; <span class="hljs-number">0</span>)&#123;
            <span class="hljs-comment">// 计算cur(10叉树的一个根节点)到cur + 1之间的数字个数</span>
            <span class="hljs-keyword">int</span> cnt = countNode(n,cur,cur+<span class="hljs-number">1</span>);
            <span class="hljs-keyword">if</span>(k &gt;= cnt)&#123; <span class="hljs-comment">//cur游标在树上同一层向右移动</span>
                k -= cnt;
                cur += <span class="hljs-number">1</span>;
            &#125;<span class="hljs-keyword">else</span>&#123;
                k -= <span class="hljs-number">1</span>; <span class="hljs-comment">// 去除当前根,向下探索子树</span>
                cur *=<span class="hljs-number">10</span>; <span class="hljs-comment">// 游标向下移动,孩子节点代表的数值需要乘以10 </span>
            &#125;
        &#125;
        <span class="hljs-keyword">return</span> cur;
    &#125;
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">countNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-keyword">long</span> l, <span class="hljs-keyword">long</span> r)</span></span>&#123;
        <span class="hljs-comment">//小细节,注意溢出,min函数强制转换一下long</span>
        <span class="hljs-keyword">int</span> cnt = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">while</span>(l&lt;=n)&#123;
            cnt += min(<span class="hljs-keyword">long</span>(n+<span class="hljs-number">1</span>), r) - l; <span class="hljs-comment">// 计数区间为左闭右开[l,r)</span>
            l*=<span class="hljs-number">10</span>;
            r*=<span class="hljs-number">10</span>;
        &#125;
        <span class="hljs-keyword">return</span> cnt; <span class="hljs-comment">//返回该结点下的node数</span>
    &#125;
&#125;;</code></pre></div>
<blockquote>
<p>变式：<font color = "#FF0000">!下次问一下，给忘记了</font></p>
<p>给定<span class="math inline">\(n\)</span>个不相同的整数<span class="math inline">\(a_1,a_2,...,a_n\)</span>和<span class="math inline">\(k\)</span>，<span class="math inline">\(max\{a_i\} &lt; 10000\)</span>。找到<span class="math inline">\(a_1\)</span>到<span class="math inline">\(a_n\)</span>中字典序第<span class="math inline">\(k\)</span>小的数字。注意：<span class="math inline">\(1 \leq k \leq n\)</span></p>
<p>提示：桶排序、堆排序、快速搜索、线性时间选择</p>
</blockquote>
<hr />
<h3 id="月21日-mathematical-basis">9月21日 Mathematical Basis</h3>
<ul>
<li><p>评估算法的执行效率：经验（Empirical）与理论（Theoretical）</p></li>
<li><p>渐进分析符号</p>
<ol type="1">
<li><p>渐近上界记号 $ $</p>
<p>若存在两个正常数 <span class="math inline">\(c\)</span> 和 <span class="math inline">\(n_0\)</span> ，使得对所有的 <span class="math inline">\(n \geq n_0\)</span> ，都有： <span class="math inline">\(f(n) \le c \times g(n)\)</span> ，则称 <span class="math inline">\(f(n) = \Omicron(g(n))\)</span> 。</p></li>
<li><p>渐近下界记号 <span class="math inline">\(\Omega\)</span></p>
<p>若存在两个正常数 <span class="math inline">\(c\)</span> 和 <span class="math inline">\(n_0\)</span> ，使得对所有的 <span class="math inline">\(n \geq n_0\)</span> ，都有： <span class="math inline">\(f(n) \ge c \times g(n)\)</span> ，则称 <span class="math inline">\(f(n) = \Omega(g(n))\)</span> 。</p></li>
<li><p>紧渐近界记号 <span class="math inline">\(\Theta\)</span></p>
<p>若存在三个正常数 <span class="math inline">\(c_1\)</span>、<span class="math inline">\(c_2\)</span> 和 <span class="math inline">\(n_0\)</span> ，使得对所有的 <span class="math inline">\(n \geq n_0\)</span> ，都有： <span class="math inline">\(c_1 \times g(n) \ge f(n) \ge c_2 \times g(n)\)</span> ，则称 <span class="math inline">\(f(n) = \Theta(g(n))\)</span> 。</p></li>
<li><p>非紧上界记号 $ $</p>
<p><span class="math inline">\(\omicron(g(n))=\{f(n) |C1\}\)</span> ，其中 <span class="math inline">\(C1\)</span> : 对于任何正常数 <span class="math inline">\(c &gt; 0\)</span>，存在正数<span class="math inline">\(n_0 &gt; 0\)</span>使得对所有<span class="math inline">\(n \ge n_0\)</span> 有<span class="math inline">\(0 \le f(n) &lt; c \times g(n)\)</span> 。</p>
<p>等价于 <span class="math inline">\(\lim_{ n \to \infty}{f(n)/g(n) \to 0}\)</span></p></li>
<li><p>非紧下界记号 <span class="math inline">\(\omega\)</span></p>
<p><span class="math inline">\(\omega(g(n))=\{f(n) |C2\}\)</span> ，其中 <span class="math inline">\(C2\)</span> : 对于任何正常数 <span class="math inline">\(c &gt; 0\)</span>，存在正数<span class="math inline">\(n_0 &gt; 0\)</span>使得对所有<span class="math inline">\(n \ge n_0\)</span> 有<span class="math inline">\(0 \le c \times g(n) &lt; f(n)\)</span> 。</p>
<p>等价于 <span class="math inline">\(\lim_{ n \to \infty}{f(n)/g(n) \to \infty}\)</span></p></li>
</ol></li>
<li><p>Master Theorem ★</p>
<p><img src="Snipaste_2020-09-28_20-57-02.png" srcset="/img/loading.gif" /></p>
<p>主要目的是比较等号右侧的两项函数那个作为“主导”，精简如下。</p>
<p><span class="math inline">\(\begin{aligned}  \text { If } T(n)=a T\left(\left\lceil\frac{n}{b}\right\rceil\right)+O\left(n^{d}\right) \text { (for constants} \; a&gt;0, b&gt;1, d \geq 0), \text { then: }  \end{aligned}\)</span></p>
<div class="hljs"><pre><code>$T(n)=\left\&#123;\begin&#123;array&#125;&#123;ll&#125;</code></pre></div>
<p>O(n^{d}) &amp;  d&gt;<em>{b} a \ O(n^{d} n) &amp;  d=</em>{b} a \ O(n^{<em>{b} a}) &amp;  d&lt;</em>{b} a \end{array}.$ . （证明参见：<a target="_blank" rel="noopener" href="https://brilliant.org/wiki/master-theorem/">brilliant</a> <a target="_blank" rel="noopener" href="https://www.coursera.org/lecture/algorithmic-toolbox/proof-of-the-master-theorem-7KR1r">Coursera</a> ）</p></li>
<li><p>等待写master定理求解的例子</p></li>
</ul>
<h3 id="月28日-devide-and-conquer-algorithm">9月28日 Devide And Conquer Algorithm</h3>
<p>==10.10课结束补==</p>
<ul>
<li><p>分治算法原理</p>
<p>三步走：Devide-Conquer-Combine</p>
<p>递归方程：<span class="math inline">\(T(n) = aT(n/b)+D(n)+C(n)\)</span> ，右侧为分治复杂度、问题划分划分复杂度和合并复杂度。</p></li>
<li><p>二分搜索</p>
<p>见《算法整理》lower_bound写法。</p></li>
<li><p>大整数乘法</p>
<p><span class="math inline">\(n\)</span> 位K进制整数X和Y相乘。</p>
<p>解决方法：</p>
<ol type="1">
<li>模拟小学乘法：最简单的乘法竖式手算的累加型；</li>
<li>分治乘法：最简单的是Karatsuba乘法，一般化以后有Toom-Cook乘法；</li>
<li>快速傅里叶变换FFT：（为了避免精度问题，可以改用快速数论变换FNTT），时间复杂度 <span class="math inline">\(O(N lgN lglgN)\)</span> 。具体可参照<a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm">Schönhage–Strassen algorithm</a>；</li>
<li>中国剩余定理：把每个数分解到一些互素的模上，然后每个同余方程对应乘起来就行；</li>
<li>Furer's algorithm：在渐进意义上FNTT还快的算法。不过好像不太实用，本文就不作介绍了。大家可以参考维基百科<a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm">Fürer's algorithm</a>。</li>
</ol>
<p>参考<a target="_blank" rel="noopener" href="https://blog.csdn.net/u010983881/article/details/77503519">博客</a></p></li>
<li><p>矩阵乘法</p></li>
<li><p>求第k小元素问题</p></li>
<li><p>寻找最近点对</p></li>
<li><p>FFT - 快速傅里叶变换</p></li>
<li><p>寻找凸包</p></li>
</ul>
<blockquote>
<p>思考题 1</p>
<p>LeetCode 240 <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/search-a-2d-matrix-ii/">搜索二维矩阵 II</a></p>
<p>使用二分的方式削减搜索空间，分别对<span class="math inline">\(row\)</span>维度和<span class="math inline">\(colume\)</span>维度进行二分，使用lower_bound的二分写法来求<span class="math inline">\(row\)</span>和<span class="math inline">\(col\)</span>方向上的<span class="math inline">\(target\)</span>下界（第一个大于等于<span class="math inline">\(target\)</span>的数的位置是<span class="math inline">\(l\)</span>）。需要特别判断的是</p>
</blockquote>
<div class="hljs"><pre><code class="hljs C++"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span> <span class="hljs-comment">//196 ms  10.6s MB</span>
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">searchMatrix</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; matrix, <span class="hljs-keyword">int</span> target)</span> </span>&#123;
        <span class="hljs-keyword">if</span>(matrix.size()==<span class="hljs-number">0</span> || matrix[<span class="hljs-number">0</span>].size()==<span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        <span class="hljs-keyword">return</span> binarySearch(matrix, matrix.size(), <span class="hljs-number">0</span>, target);  
    &#125;
    <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">binarySearch</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; matrix, <span class="hljs-keyword">int</span> row, <span class="hljs-keyword">int</span> col, <span class="hljs-keyword">int</span> target)</span></span>&#123;
        <span class="hljs-keyword">int</span> next_row, next_col;
        <span class="hljs-keyword">int</span> l = <span class="hljs-number">0</span>, r = row;
        <span class="hljs-keyword">while</span>(l &lt; r)&#123; <span class="hljs-comment">//[0,r)</span>
            <span class="hljs-keyword">int</span> mid = l + (r - l) / <span class="hljs-number">2</span>;
            <span class="hljs-keyword">if</span>(matrix[mid][col] &gt;= target)&#123;
                r = mid;
            &#125;<span class="hljs-keyword">else</span> &#123; 
                l = mid + <span class="hljs-number">1</span>;
            &#125;
        &#125;
        
        <span class="hljs-keyword">if</span>(l &lt; row &amp;&amp; matrix[l][col]==target) <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;<span class="hljs-comment">//判断row方向的下界数字是否是target</span>
        next_row = l; <span class="hljs-comment">// 求lower_bound</span>
        <span class="hljs-keyword">if</span>(next_row == <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>; <span class="hljs-comment">// 判断row是否越界，即row方向数组为空</span>

        l = col, r = matrix[<span class="hljs-number">0</span>].size();
        <span class="hljs-keyword">while</span>(l &lt; r)&#123;
            <span class="hljs-keyword">int</span> mid = l + (r - l) / <span class="hljs-number">2</span>;
            <span class="hljs-keyword">if</span>(matrix[next_row<span class="hljs-number">-1</span>][mid]&gt;=target)&#123;
                r = mid;
            &#125;<span class="hljs-keyword">else</span>&#123;
                l = mid+<span class="hljs-number">1</span>;
            &#125;
        &#125;
        <span class="hljs-keyword">if</span>(l == matrix[<span class="hljs-number">0</span>].size()) <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>; <span class="hljs-comment">//判断col是否越界,即col方向数组为空</span>
        next_col = l;
        
        <span class="hljs-keyword">return</span> binarySearch(matrix, next_row, next_col,target);<span class="hljs-comment">//左下角顶点坐标至右上角顶点</span>
    &#125;
&#125;;</code></pre></div>
<div class="hljs"><pre><code class="hljs C++"><span class="hljs-comment">//从左下角开始，每次删除一行或一列</span>
</code></pre></div>
<blockquote>
<p>思考题 2</p>
<p>LeetCode - 4 - <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/">寻找两个正序数组的中位数</a> - 官方<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/">题解</a></p>
<p>思路：要实现 <span class="math inline">\(\Omicron(log(m+n))\)</span> 的复杂度，首先考虑二分。中位数的作用是将一组有序样本划分为两个相等长度的部分，所以该问题可以转化为求一个 <span class="math inline">\(m+n\)</span> 长度的数组的第 <span class="math inline">\(k\)</span> 小数（如果下标是0始，则对应下标为 <span class="math inline">\(k-1\)</span> 的数），其中 <span class="math inline">\(k = (m+n+1)/2\)</span> （总数为奇数，下标0始）或者 <span class="math inline">\(k=(m+n)/2,k=(m+n)/2+1\)</span>（总数为偶数，下标0始，取平均）。</p>
<p>那么神奇的操作来了，此处，我们二分的对象是区间长度 <span class="math inline">\(k\)</span> ，每次从数组 <span class="math inline">\(A\)</span> 和数组 <span class="math inline">\(B\)</span> 中取 <span class="math inline">\(k/2\)</span> 区间长度的数（下标0始，所以取到<span class="math inline">\(k/2-1\)</span>），然后比较 <span class="math inline">\(A[k/2-1]、B[k/2-1]\)</span> 的大小，分以下三种情况讨论区间的取舍问题。</p>
<ol type="1">
<li><span class="math inline">\(A[k/2-1] &lt; B[k/2-1]\)</span> ，舍弃区间 <span class="math inline">\(A[0:k/2-1]\)</span></li>
<li><span class="math inline">\(A[k/2-1] &gt; B[k/2-1]\)</span> ，舍弃区间 <span class="math inline">\(B[0:k/2-1]\)</span><br />
</li>
<li><span class="math inline">\(A[k/2-1] = B[k/2-1]\)</span> ，可归入（1）或（2）</li>
</ol>
<p>Q：为什么比较两个有序区间的最大值就可以直接舍去其中一个区间呢？</p>
<p>A：已知<span class="math inline">\(A[0:k/2-1]、B[0:k/2-1]\)</span> 两段区间共计 <span class="math inline">\(k\)</span> 个数字，以（1）为例，<span class="math inline">\(A[k/2-1]\)</span>较小，所以在它之前的数字都不可能是第 <span class="math inline">\(k\)</span> 小的，可舍去，由于<span class="math inline">\(A[k/2-1] &lt; B[k/2-1]\)</span>，区间 <span class="math inline">\(B[0:k/2-1]\)</span> 中至少存在一个数字大于 <span class="math inline">\(A[k/2-1]\)</span> ，即 <span class="math inline">\(A[k/2-1]\)</span> 最多是第 <span class="math inline">\(k-1\)</span> 大的，舍去 <span class="math inline">\(A[0:k/2-1]\)</span> 不会影响寻找第 <span class="math inline">\(k\)</span> 小的数字。那么，当<span class="math inline">\(A[k/2-1] &lt; B[k/2-1]\)</span> ，说明第 <span class="math inline">\(k\)</span> 个数位于 <span class="math inline">\(A\)</span> 数组的第 <span class="math inline">\(k / 2\)</span> 个数后半段，或者 <span class="math inline">\(b\)</span> 数组的 第 <span class="math inline">\(k / 2\)</span> 个数前半段，问题规模缩小了一半，然后递归处理子问题就行。</p>
</blockquote>
<div class="hljs"><pre><code class="hljs C++"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> &#123;</span> <span class="hljs-comment">//这不是我写的，我晚点按照这个思路试着重写</span>
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getKthElement</span><span class="hljs-params">(<span class="hljs-keyword">const</span> <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums1, <span class="hljs-keyword">const</span> <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums2, <span class="hljs-keyword">int</span> k)</span> </span>&#123;
        <span class="hljs-comment">/* 主要思路：要找到第 k (k&gt;1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较</span>
<span class="hljs-comment">         * 这里的 &quot;/&quot; 表示整除</span>
<span class="hljs-comment">         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个</span>
<span class="hljs-comment">         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个</span>
<span class="hljs-comment">         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) &lt;= k-2 个</span>
<span class="hljs-comment">         * 这样 pivot 本身最大也只能是第 k-1 小的元素</span>
<span class="hljs-comment">         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 &quot;删除&quot;，剩下的作为新的 nums1 数组</span>
<span class="hljs-comment">         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 &quot;删除&quot;，剩下的作为新的 nums2 数组</span>
<span class="hljs-comment">         * 由于我们 &quot;删除&quot; 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数</span>
<span class="hljs-comment">         */</span>

        <span class="hljs-keyword">int</span> m = nums1.size();
        <span class="hljs-keyword">int</span> n = nums2.size();
        <span class="hljs-keyword">int</span> index1 = <span class="hljs-number">0</span>, index2 = <span class="hljs-number">0</span>;

        <span class="hljs-keyword">while</span> (<span class="hljs-literal">true</span>) &#123;
            <span class="hljs-comment">// 边界情况</span>
            <span class="hljs-keyword">if</span> (index1 == m) &#123;
                <span class="hljs-keyword">return</span> nums2[index2 + k - <span class="hljs-number">1</span>];
            &#125;
            <span class="hljs-keyword">if</span> (index2 == n) &#123;
                <span class="hljs-keyword">return</span> nums1[index1 + k - <span class="hljs-number">1</span>];
            &#125;
            <span class="hljs-keyword">if</span> (k == <span class="hljs-number">1</span>) &#123;
                <span class="hljs-keyword">return</span> min(nums1[index1], nums2[index2]);
            &#125;

            <span class="hljs-comment">// 正常情况</span>
            <span class="hljs-keyword">int</span> newIndex1 = min(index1 + k / <span class="hljs-number">2</span> - <span class="hljs-number">1</span>, m - <span class="hljs-number">1</span>);
            <span class="hljs-keyword">int</span> newIndex2 = min(index2 + k / <span class="hljs-number">2</span> - <span class="hljs-number">1</span>, n - <span class="hljs-number">1</span>);
            <span class="hljs-keyword">int</span> pivot1 = nums1[newIndex1];
            <span class="hljs-keyword">int</span> pivot2 = nums2[newIndex2];
            <span class="hljs-keyword">if</span> (pivot1 &lt;= pivot2) &#123;
                k -= newIndex1 - index1 + <span class="hljs-number">1</span>;
                index1 = newIndex1 + <span class="hljs-number">1</span>;
            &#125;
            <span class="hljs-keyword">else</span> &#123;
                k -= newIndex2 - index2 + <span class="hljs-number">1</span>;
                index2 = newIndex2 + <span class="hljs-number">1</span>;
            &#125;
        &#125;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">double</span> <span class="hljs-title">findMedianSortedArrays</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums1, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums2)</span> </span>&#123;
        <span class="hljs-keyword">int</span> totalLength = nums1.size() + nums2.size();
        <span class="hljs-keyword">if</span> (totalLength % <span class="hljs-number">2</span> == <span class="hljs-number">1</span>) &#123;
            <span class="hljs-keyword">return</span> getKthElement(nums1, nums2, (totalLength + <span class="hljs-number">1</span>) / <span class="hljs-number">2</span>);
        &#125;
        <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-keyword">return</span> (getKthElement(nums1, nums2, totalLength / <span class="hljs-number">2</span>) + getKthElement(nums1, nums2, totalLength / <span class="hljs-number">2</span> + <span class="hljs-number">1</span>)) / <span class="hljs-number">2.0</span>;
        &#125;
    &#125;
&#125;;</code></pre></div>
<h3 id="np完全性">NP完全性</h3>
<ol type="1">
<li><p>P与NP</p>
<ul>
<li><p>P类问题可以用多项式时间的确定性算法进行判定或求解。（多项式时间可解）</p>
<p>Polynomial</p></li>
<li><p>NP类问题可用多项式时间的非确定性算法进行判定或求解。（多项式时间可验证）</p>
<p>Non-deterministic Polynomial</p></li>
<li><p>判定问题：仅要求回答"yes"与"no"(证比求易) <span class="math inline">\(P \subseteq NP\)</span></p></li>
</ul>
<p><font color='#FF0000'>所有NP 问题都是判定问题，回答 yes 或 no</font></p></li>
<li><p>经典问题 (NP-completeness )</p>
<p><a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/List_of_NP-complete_problems">List of NP-complete problems</a></p>
<p>SAT 问题 (Boolean Satisfiability) - 第一个NP-C</p>
<p>最大团问题 (Maximum Clique)</p>
<p>图着色问题 (Graph Coloring)</p>
<p>哈密顿回路问题 (Hamiltonian Cycle)</p>
<p>TSP 问题 (Traveling Salesman)</p>
<p>顶点覆盖问题 (Vertex Cover)</p>
<p>最长路径问题 (Longest Path)</p>
<p>子集和问题 (Sum of Subset)</p>
<p><img src="Snipaste_2020-12-24_14-25-21.png" srcset="/img/loading.gif" /></p>
<p>若某个NP完全问题多项式时间可解，则所有NP问题均可多项式时间求解，从而有P=NP。</p>
<p><img src="Snipaste_2020-12-24_14-31-07.png" srcset="/img/loading.gif" /></p></li>
<li><p>规约 Reduction</p>
<p>一个问题A可以归约为问题B的含义是，可用问题B的解法解决问题A，或者说，问题A可以“变成”问题B；举个例子，一元一次方程求解可以归约化为一元二次方程求解。（B的复杂度大于等于A的复杂度）</p></li>
</ol>
<h3 id="近似算法">近似算法</h3>
<p>经典问题：顶点覆盖，集合覆盖，旅行商问题，子集和问题，随机和线性规划。</p>
<p>定义：能够给出一个优化问题的近似优化解的算法，主要解决优化问题（最大化和最小化）</p>
<p>评价指标（近似度）：Ratio Bound，相对误差。</p>
<p><img src="Snipaste_2020-12-24_15-55-46.png" srcset="/img/loading.gif" /></p>
<p><img src="Snipaste_2020-12-24_15-56-16.png" srcset="/img/loading.gif" /></p>
<p>满足 <span class="math inline">\(\epsilon(n) \le B(n)-1\)</span> (最小化问题时<span class="math inline">\(\epsilon(n) = B(n)-1\)</span>)，只要求出了RB就可以得出相对误差。</p>
<p>参考资料 <a target="_blank" rel="noopener" href="https://zhpmatrix.github.io/2016/10/28/np-problem/">[1]</a></p>
<ol type="1">
<li><p>顶点覆盖</p>
<p>选取若干个点组成集合A，其所连接的边可以把改图的所有点都囊括，希望|A|尽可能地小。</p>
<p>近似的方法是随机选取一条边<span class="math inline">\((u,v)\)</span>，删除与u或v相连的边，将每一条边的两个端点加入A，重复直到无边可删，由于每次都会加入两个点加入A，所以近似比为2。</p>
<p>可以用线性规划来做，原问题可以转化为0-1整数规划问题，但是可以适当放宽条件，是的<span class="math inline">\(x(v)\)</span>取值为浮点数。（整数规划是NP完全的，线性规划是多项式可解的）</p></li>
<li><p>集合覆盖问题</p>
<p>有限集合<span class="math inline">\(U=\{1,2,...,n\}\)</span>，子集和的集合<span class="math inline">\(S=\{ s_1, s_2, ...,s_m\}\)</span> , <span class="math inline">\(s_i \subseteq U\)</span> ，求集合<span class="math inline">\(A\subseteq S\)</span> ,满足元素完全覆盖U.</p>
<p>近似的方法是每次迭代选择能覆盖最多未被覆盖元素的子集。</p>
<p><img src="Snipaste_2020-12-24_16-58-50.png" srcset="/img/loading.gif" /></p></li>
<li><p>旅行商问题</p>
<p>给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)，要找出G的最小费用哈密顿回路。</p>
<p>近似算法需利用一个性质（三角不等式）：费用函数<span class="math inline">\(c\)</span>通常意义下具有三角不等式性质，即对任意的3个顶点<span class="math inline">\(u,v,w∈V\)</span>，有：<span class="math inline">\(c(u,w)≤c(u,v)+c(v,w)\)</span>。</p>
<p><img src="Snipaste_2020-12-24_17-32-36.png" srcset="/img/loading.gif" /></p></li>
<li><p>子集和问题</p>
<p><span class="math inline">\(S=\{x_1,x_2,...,x_n\}\)</span>是一个正整数的集合，t是一个正整数。子集和问题判定是否存在S的一个子集<span class="math inline">\(S_1\)</span>，使得<span class="math inline">\(S_1\)</span>中的元素和等于t。</p></li>
<li><p>Max-3CNF</p>
<p><img src="Snipaste_2020-12-24_17-39-42.png" srcset="/img/loading.gif" /></p></li>
</ol>
<h3 id="随机算法">随机算法</h3>
<p>随机算法是一种使用概率和统计方法在其执行过程中对于下一步计算做出随机选择的算法。</p>
<ol type="1">
<li><p>随机算法分类</p>
<p>随机数值算法、Monte Carlo算法、Las Vegas算法、Sherwood算法</p>
<ul>
<li><p>随机数值算法</p>
<p>主要用于数值问题求解，往往输出近似解，且精确度与执行时间成正比。</p>
<p>e.g. 计算<span class="math inline">\(\pi\)</span>（正方形与四分之一圆、投针实验计算）、计算积分（强大数定律）</p></li>
<li><p>Mente Carlo算法</p>
<p>主要用于需要准确解的问题，<font color='#FF0000'>算法可能给出错误的解</font>，且获得精确解的概率与算法执行时间成正比。</p>
<p>e.g. 求主元素（一半以上的元素都是<span class="math inline">\(x\)</span>）MC算法执行<span class="math inline">\(k\)</span>次，算法发生错误的概率为<span class="math inline">\(2^{(-k)}\)</span> 参考资料 <a target="_blank" rel="noopener" href="https://blog.csdn.net/chensanwa/article/details/78657163">非随机算法</a> （传统算法就是对每一个数字都去从头到尾遍历一遍，很傻，所以复杂度是<span class="math inline">\(\Omicron(n^2)\)</span>）、判断字符串是否相等（去指纹，错判率）、字符串匹配、素数测试（Fermat小定理）</p>
<p><img src="Snipaste_2020-12-24_20-39-30.png" srcset="/img/loading.gif" /></p>
<p><img src="Snipaste_2020-12-24_20-56-54.png" srcset="/img/loading.gif" /></p></li>
<li><p>Sherwood算法</p>
<p>一定可求一个正确解，确定算法的最坏与平均复杂性差别很大，加入随机性即得到Sherwood算法。作用是消除最坏行为和特定实例的联系。</p>
<p>e.g. 快速排序，每次随机选取一个基准数字。</p></li>
<li><p>Las Vegas算法</p>
<p>一旦找到一个解，该解一定是正确的，且找到解的概率与执行时间成正比，增加对问题反复求解次数，可使求解无效的概率任意小。</p>
<p>e.g. 求第<span class="math inline">\(k\)</span>小元素2（若以等概率方法从<span class="math inline">\(n\)</span>个数中随机取数，则该算法比较次数的期望不超过<span class="math inline">\(4n\)</span>）</p>
<p><img src="Snipaste_2020-12-24_20-23-32.png" srcset="/img/loading.gif" /></p></li>
</ul></li>
</ol>

            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a>
                    
                  </div>
                
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2021/06/30/2021-06-30-GNN%E8%AE%BA%E6%96%87%E6%B8%85%E5%8D%95/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">图神经网络论文清单</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2020/09/19/2020-09-19-%E5%88%86%E5%B8%83%E5%BC%8F%E8%AE%AD%E7%BB%83%E6%8A%80%E6%9C%AF%E6%80%BB%E7%BB%93/">
                        <span class="hidden-mobile">分布式训练技术总结</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="" target="_blank" rel="nofollow noopener"><span>_____</span></a>
      <i class="iconfont icon-love"></i>
      <a href="" target="_blank" rel="nofollow noopener">
        <span>digua</span></a>
    </div>
    

    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>







  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "金总的算法课&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  
















</body>
</html>
